翻訳と辞書 Words near each other ・ Log, Slovenia ・ Log-Cauchy distribution ・ Log-concave ・ Log-distance path loss model ・ Log-Laplace distribution ・ Log-linear analysis ・ Log-linear model ・ Log-logistic distribution ・ Log-net ・ Log-normal distribution ・ Log-periodic antenna ・ Log-polar coordinates ・ Log-rank test ・ Log-space computable function ・ Log-space reduction ・ Log-space transducer ・ Log-spectral distance ・ Log-structured file system ・ Log-structured File System (BSD) ・ Log-structured merge-tree ・ Log4j ・ Log5 ・ Loga ・ Loga Department ・ Loga Nayaga Shani Eswaran shrine ・ Loga Ramin Torkian ・ Logabirum ・ Logacta ・ Logan ・ Logan (automobile) Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Log-space transducer ： ウィキペディア英語版 Log-space transducer A log space transducer (LST) is a type of Turing machine used for log-space reductions. A log space transducer, $M$, has three tapes: * A read-only ''input'' tape. * A read/write ''work'' tape (bounded to at most $O(\backslash log\; n)$ symbols). * A write-only, write-once ''output'' tape. $M$ will be designed to compute a log-space computable function $f\backslash colon\; \backslash Sigma^\backslash ast\; \backslash rightarrow\; \backslash Sigma^\backslash ast$ (where $\backslash Sigma$ is the alphabet of both the ''input'' and ''output'' tapes). If $M$ is executed with $w$ on its ''input'' tape, when the machine halts, it will have $f(w)$ remaining on its ''output'' tape. A language $A\; \backslash subseteq\; \backslash Sigma^\backslash ast$ is said to be log-space reducible to a language $B\; \backslash subseteq\; \backslash Sigma^\backslash ast$ if there exists a log-space computable function, $f$, which will convert an input from problem $A$ into an input to problem $B$. I.E. $w\; \backslash in\; A\; \backslash iff\; f(w)\; \backslash in\; B$. This seems like a rather convoluted idea, but it has two useful properties that are desirable for a reduction: # The property of transitivity holds. (A reduces to B and B reduces to C implies A reduces to C). # If A reduces to B, and B is in L, then we know A is in L. Transitivity holds because it is possible to feed the output tape of one reducer (A->B) to another (B->C). At first glance, this seems incorrect because the A->C reducer needs to store the output tape from the A->B reducer onto the work tape in order to feed it into the B->C reducer, but this is not true. Each time the B->C reducer needs to access its input tape, the A->C reducer can re-run the A->B reducer, and so the output of the A->B reducer never needs to be stored entirely at once. ==References== *Szepietowski, Andrzej (1994), ''(Turing Machines with Sublogarithmic Space )'', Springer Press, ISBN 3-540-58355-6. Retrieved on 2008-12-03. *Sipser, Michael (2012), ''(Introduction to the Theory of Computation )'', Cengage Learning, ISBN 978-0-619-21764-8. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Log-space transducer」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.